In computer networks, routing protocols are used to communicate route information dynamically as networking devices such as routers are added or removed from the network. Routers may build packets or messages known as link-state packets (LSPs) based upon their local interfaces, and an LSP packet describes the router's interfaces and neighbors in the network (i.e., adjacent routers). Typically, an LSP message includes the name of the router that originated the LSP packet, a sequence number, and a list of “links” or neighboring routers.
Each router uses a conventional “flooding” algorithm to transmit its LSPs to adjacent neighbors, and the LSPs are passed along unchanged to other adjacent routers until all the routers in the area have received them. When collected together, the LSPs can be used to describe the topology of the network.
Each router maintains a link-state database (LSDB) that includes all the LSPs the router has received. When a change in the network topology occurs, a corresponding change in one or more of the LSPs will follow.
Designated routers send packets known as CSNP packets (complete sequence number protocol data units (PDUs)) to other routers in order to maintain database synchronization relating to network topology information. CSNP packets include as all the link states known to the router sending the CSNP packets. For instance, in the routing protocol IS-IS (Intermediate System to Intermediate System), designated routers send CSNP packets for ensuring that all routers participating in the protocol have a complete copy of the link state database. Typically, a CSNP message includes entries that each have a source identification (LSP IDs, identifying the source router for this respective LSP) and a sequence number corresponding to the LSP.
Each router that receives CSNP packets compares the list of link states (i.e., from the LSPIDs and the sequence numbers) in the CSNP packets with its own internal link state database. For instance, a mismatch in a sequence number in a router receiving a CSNP indicates that the receiving router may not have the most current link state as reported by another router in the network. Differences are resolved by either transmitting LSPs in the receiver's database or by transmitting a request (in the form of a partial sequence number (PSNP)) to another router for transmission of the missing LSPs.
CSNP packets or messages are sent periodically based on a CSNP interval timer which defines the number of seconds between transmissions of CSNP packets from an interface. Periodic CSNP transmission is required on local area networks (LANs) by the IS-IS specification. Conventionally, periodic CSNP packet transmission is implemented in a router by the using CPU resources to walk its link state database and rebuild the resulting the CSNP packets every time a CSNP timer expires. For instance, as shown in FIG. 1, a conventional router 10 includes an IS-IS software process 12 which operatively includes a link-state database 14 and a periodic CSNP function 16.
As topologies have grown more dense, however, there have been scaling issues. As recognized by the present inventors, there are a number of issues that make periodic CSNP transmission problematic. The CSNP interval on a given interface is configurable, the maximum transmission unit (MTU) on various interfaces might not be identical, and there may be hundreds if not thousands of interfaces or links such as peer-to-peer links (P2P) to support. Furthermore, the amount of CPU time that can be devoted to the CSNP processing can be quite limited. Rebuilding the CSNP packets by walking a link state database after every expired CSNP timer may require excessive CPU resources of a router.
Accordingly, as recognized by the present inventors, what is needed is a method and apparatus that provides periodic CSNP functionality while reducing CPU consumption and increasing scalability.
The features, utilities and advantages of the various embodiments of the invention will be apparent from the following more particular description of embodiments of the invention as illustrated in the accompanying drawings.